Code Challenge Season 1

InnerProduct (Lv. 1)
https://school.programmers.co.kr/learn/courses/30/lessons/70128
#include <cstdio>
#include <cstdbool>
#include <cstdlib>
#include <cassert>
#include <iostream>
int solution(int a[], size_t a_len, int b[], size_t b_len){
int answer=0;
assert(a_len==b_len);
for(int i=0; i<a_len; ++i){
answer+=a[i]*b[i];
}
return answer;
}
int main(void){
int a[]={1, 2, 3, 4};
int b[]={-3, -1, 0, 2};
size_t a_len, b_len;
a_len=sizeof(a)/sizeof(int);
b_len=sizeof(b)/sizeof(int);
int result=solution(a, a_len, b, b_len);
std::cout<<"Result: "<<result<<std::endl;
return 0;
}
repeatly Binary Transformation (Lv. 2)
https://school.programmers.co.kr/learn/courses/30/lessons/70129
#include <cstdio>
#include <cstdbool>
#include <cstdlib>
#include <iostream>
#include <stack>
void modify(char s[], int* ans){
int zero=0, one=0, i=0;
while(1){
if(s[i]=='0') zero++;
else if(s[i]=='1') one++;
else break;
i++;
}
ans[0]++;
ans[1]+=zero;
s[0]='\0';
std::stack<int> ss;
while(one!=0){
if(one%2==1) ss.push(1);
else ss.push(0);
one/=2;
}
char buf[64];
while(!ss.empty()){
sprintf(buf, "%d", ss.top());
strcat(s, buf);
ss.pop();
}
}
int* solution(const char* s){
int* answer=(int*)malloc(sizeof(int)*2);
char str[64];
strcpy(str, s);
answer[1]=0; // count
answer[0]=0; // zeros
while(strcmp(str, "1")){
modify(str, answer);
}
return answer;
}
int main(void){
char s1[]="110010101001";
char s2[]="01110";
char s3[]="1111111";
int* answer1=solution(s1);
int* answer2=solution(s2);
int* answer3=solution(s3);
std::cout<<"{"<<answer1[0]<<", "<<answer1[1]<<"}"<<std::endl;
std::cout<<"{"<<answer2[0]<<", "<<answer2[1]<<"}"<<std::endl;
std::cout<<"{"<<answer3[0]<<", "<<answer3[1]<<"}"<<std::endl;
return 0;
}
Flip Ternary base number (Lv. 1)
https://school.programmers.co.kr/learn/courses/30/lessons/68935
#include <iostream>
#include <vector>
#include <cmath>
int solution(int n){
int answer=0;
std::vector<int> stk;
while(n!=0){
stk.push_back(n%3);
n/=3;
}
for(int i=0; i<stk.size(); ++i){
answer+=pow(3, stk.size()-i-1)*stk[i];
}
return answer;
}
int main(void){
int n1=45;
int n2=125;
int result1, result2;
result1=solution(n1);
result2=solution(n2);
std::cout<<"result1: "<<result1<<std::endl;
std::cout<<"result2: "<<result2<<std::endl;
return 0;
}
Select two and added (Lv. 1)
https://school.programmers.co.kr/learn/courses/30/lessons/68644
#include <iostream>
#include <vector>
std::vector<int> solution(int numbers[], size_t numbers_len){
std::vector<int> result;
for(int i=0; i<numbers_len; ++i){
for(int j=i+1; j<numbers_len; ++j){
if(result.end()==find(result.begin(), result.end(), numbers[i]+numbers[j])) result.push_back(numbers[i]+numbers[j]);
}
}
sort(result.begin(), result.end());
return result;
}
int main(void){
int numbers1[]={2, 1, 3, 4, 1};
int numbers2[]={5, 0, 2, 7};
size_t size1, size2;
size1=sizeof(numbers1)/sizeof(int);
size2=sizeof(numbers2)/sizeof(int);
std::vector<int> result1=solution(numbers1, size1);
std::vector<int> result2=solution(numbers2, size2);
std::cout<<"result1: ";
for(int i=0; i<result1.size(); ++i) std::cout<<result1[i]<<' ';
std::cout<<'\n';
std::cout<<"result2: ";
for(int i=0; i<result2.size(); ++i) std::cout<<result2[i]<<' ';
std::cout<<std::endl;
return 0;
}
Compress Quad and Count it (Lv. 2)
https://school.programmers.co.kr/learn/courses/30/lessons/68936
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
int check(vector<vector<int>>& arr, vector<int> point, int size){
int y=point[0], x=point[1];
int crt=arr[y][x];
if(crt==-1) return -1;
for(int i=0; i<size; ++i){
for(int j=0; j<size; ++j){
if(arr[y+i][x+j]!=crt) return -1;
}
}
for(int i=0; i<size; ++i){
for(int j=0; j<size; ++j){
arr[y+i][x+j]=-1;
}
}
return crt;
}
vector<int> solution(vector<vector<int>> arr, size_t arr_rows, size_t arr_cols){
vector<int> answer={0, 0};
assert(arr_rows==arr_cols);
int zero=0, one=0, crt;
int n=arr_rows;
while(n!=1){
n/=2;
for(int i=0; i<arr_rows; i+=n){
for(int j=0; j<arr_cols; j+=n){
vector<int> point={i, j};
crt=check(arr, point, n);
if(crt==0) zero++;
if(crt==1) one++;
}
}
}
for(int i=0; i<arr_rows; ++i){
for(int j=0; j<arr_cols; ++j){
if(arr[i][j]==0) zero++;
else if(arr[i][j]==1) one++;
}
}
answer[0]=zero; answer[1]=one;
return answer;
}
int main(void){
vector<vector<int>> arr1={
{1, 1, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 1},
{1, 1, 1, 1}
};
vector<vector<int>> arr2={
{1, 1, 1, 1, 1, 1, 1, 1},
{0, 1, 1, 1, 1, 1, 1, 1},
{0, 0, 0, 0, 1, 1, 1, 1},
{0, 1, 0, 0, 1, 1, 1, 1},
{0, 0, 0, 0, 0, 0, 1, 1},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 1, 0, 0, 1},
{0, 0, 0, 0, 1, 1, 1, 1}
};
vector<int> result1=solution(arr1, arr1.size(), arr1[0].size());
vector<int> result2=solution(arr2, arr2.size(), arr2[0].size());
std::cout<<"result1: {"<<result1[0]<<", "<<result1[1]<<"}"<<std::endl;
std::cout<<"result2: {"<<result2[0]<<", "<<result2[1]<<"}"<<std::endl;
return 0;
}
Triangle Snail (Lv. 2)
https://school.programmers.co.kr/learn/courses/30/lessons/68645
#include <iostream>
#include <vector>
using namespace std;
void down(vector<vector<int>>& tri, vector<int> point, int& value, int size){
int y=point[0], x=point[1];
for(int i=0; i<size; ++i){
tri[y+i][x]=value++;
}
}
void right(vector<vector<int>>& tri, vector<int> point, int& value, int size){
int y=point[0], x=point[1];
for(int i=0; i<size; ++i){
tri[y][x+i]=value++;
}
}
void diag(vector<vector<int>>& tri, vector<int> point, int& value, int size){
int y=point[0], x=point[1];
for(int i=0; i<size; ++i){
tri[y-i][x-i]=value++;
}
}
vector<int> solution(int n){
vector<int> answer;
vector<vector<int>> tri(n, vector<int>(n, 0));
int value=1, dir=0;
vector<int> point={-1, 0};
while(n!=0){
if(dir%3==0) {
point[0]+=1;
down(tri, point, value, n);
point[0]+=n-1;
}
else if(dir%3==1) {
point[1]+=1;
right(tri, point, value, n);
point[1]+=n-1;
}
else {
point[0]-=1; point[1]-=1;
diag(tri, point, value, n);
point[0]-=n-1; point[1]-=n-1;
}
n--;
dir++;
}
for(int i=0; i<tri.size(); ++i){
for(int j=0; j<i+1; ++j){
answer.push_back(tri[i][j]);
}
}
return answer;
}
int main(void){
vector<int> result1=solution(4);
vector<int> result2=solution(5);
vector<int> result3=solution(6);
std::cout<<"result1: ";
for(int i=0; i<result1.size(); ++i){
std::cout<<result1[i]<<' ';
}
std::cout<<std::endl;
std::cout<<"result2: ";
for(int i=0; i<result2.size(); ++i){
std::cout<<result2[i]<<' ';
}
std::cout<<std::endl;
std::cout<<"result3: ";
for(int i=0; i<result3.size(); ++i){
std::cout<<result3[i]<<' ';
}
std::cout<<std::endl;
return 0;
}
Pop the Balloon (Lv. 3)
https://school.programmers.co.kr/learn/courses/30/lessons/68646
#include <iostream>
#include <vector>
using namespace std;
int checker(vector<int>& a, int pos){
int crt=a[pos], count=0;
if(pos==0 || pos==a.size()-1) return 1;
for(int i=0; i<pos; ++i){
if(a[i]<crt){
count++;
break;
}
}
for(int i=pos+1; i<a.size(); ++i){
if(a[i]<crt){
count++;
break;
}
}
if(count==2) return 0;
else return 1;
}
// 자신의 좌측과 우측에 둘다 자신 보다 작은 값이 있을 시, 불가능
int solution(vector<int> a, size_t a_len){
int answer=0;
for(int i=0; i<a_len; ++i){
if(checker(a, i)) answer++;
}
return answer;
}
int main(void){
vector<int> a1={9, -1, -5};
vector<int> a2={-16, 27, 65, -2, 58, -92, -71, -68, -61, -33};
int result1, result2;
result1=solution(a1, a1.size());
result2=solution(a2, a2.size());
cout<<"Result1: "<<result1<<endl;
cout<<"Result2: "<<result2<<endl;
return 0;
}
Star Sequence (Lv. 3)
https://school.programmers.co.kr/learn/courses/30/lessons/70130
#include <iostream>
#include <vector>
using namespace std;
void combination(vector<int> arr, vector<vector<int>>& sta, int r){
vector<bool> index(arr.size(), true);
for(int i=0; i<arr.size()-r; ++i) index[i]=false;
do{
vector<int> comb;
for(int i=0; i<arr.size(); ++i){
if(index[i]) comb.push_back(arr[i]);
}
sta.push_back(comb);
}while(next_permutation(index.begin(), index.end()));
}
int checker(vector<int> a){
if(a.size()<2) return 0;
int value=-1;
for(int i=0; i<a.size(); i+=2){
if(a[i]==a[i+1]) return 0;
}
if(a[0]==a[2]) value=a[0];
if(a[0]==a[3]) value=a[0];
if(a[1]==a[2]) value=a[1];
if(a[1]==a[3]) value=a[1];
if(value==-1) return 0;
for(int i=0; i<a.size(); i+=2){
if(a[i]==value) continue;
else if (a[i+1]==value) continue;
else return 0;
}
return 1;
}
int solution(vector<int> a, size_t a_len){
// Full Size Check!
if(checker(a)) return a.size();
vector<int> index(a.size(), 0);
for(int i=0; i<a.size(); ++i) index[i]=i;
// Combination delete and check!
for(int i=2; i<a.size(); i+=2){
vector<vector<int>> comb;
combination(index, comb, i);
for(vector<int> cc: comb){
vector<int> a_copy(a.size());
copy(a.begin(), a.end(), a_copy.begin());
// From back delete!
reverse(cc.begin(), cc.end());
for(int num: cc){
a_copy.erase(a_copy.begin()+num);
}
if(checker(a_copy)) return a_copy.size();
}
}
return 0;
}
int main(void){
vector<int> a1={0};
vector<int> a2={5, 2, 3, 3, 5, 3};
vector<int> a3={0, 3, 3, 0, 7, 2, 0, 2, 2, 0};
int result1, result2, result3;
result1=solution(a1, a1.size());
result2=solution(a2, a2.size());
result3=solution(a3, a3.size());
cout<<"Result1: "<<result1<<endl;
cout<<"Result2: "<<result2<<endl;
cout<<"Result3: "<<result3<<endl;
return 0;
}
Middle value of Tree trio (Lv. 4)
https://school.programmers.co.kr/learn/courses/30/lessons/68937
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int distance(const vector<vector<int>>& edges, int p1, int p2, int prev, int d){
vector<int> p1_near;
if(p1==p2) return d;
for(int i=0; i<edges.size(); ++i){
if(edges[i][0]==p1 && edges[i][1]!=prev){
p1_near.push_back(edges[i][1]);
continue;
}
if(edges[i][1]==p1 && edges[i][0]!=prev){
p1_near.push_back(edges[i][0]);
continue;
}
}
int tmp_d;
for(int i=0; i<p1_near.size(); ++i){
tmp_d=distance(edges, p1_near[i], p2, p1, d+1);
if(tmp_d!=0) return tmp_d;
}
return 0;
}
void combination(vector<int> arr, vector<vector<int>>& ret, int r=3){
vector<bool> index(arr.size(), true);
for(int i=0; i<arr.size()-r; ++i) index[i]=false;
do{
vector<int> comb;
for(int i=0; i<arr.size(); ++i){
if(index[i]) comb.push_back(arr[i]);
}
ret.push_back(comb);
}while(next_permutation(index.begin(), index.end()));
}
int solution(int n, vector<vector<int>> edges){
int answer=0, tmp;
vector<int> arr(n);
vector<vector<int>> combi;
for(int i=0; i<n; ++i) arr[i]=i+1;
combination(arr, combi, 3);
for(vector<int> cas: combi){
vector<int> dist;
for(int i=0; i<cas.size(); ++i){
for(int j=i+1; j<cas.size(); ++j){
tmp=distance(edges, cas[i], cas[j], 0, 0);
dist.push_back(tmp);
}
}
sort(dist.begin(), dist.end());
if(answer<dist[dist.size()/2]) answer=dist[dist.size()/2];
}
return answer;
}
int main(void){
int n1=4, n2=5, result1, result2;
vector<vector<int>> edges1={
{1, 2},
{2, 3},
{3, 4}
};
vector<vector<int>> edges2={
{1, 5},
{2, 5},
{3, 5},
{4, 5}
};
result1=solution(n1, edges1);
result2=solution(n2, edges2);
cout<<"result1: "<<result1<<endl;
cout<<"result2: "<<result2<<endl;
return 0;
}
Count even line number (Lv. 4)
https://school.programmers.co.kr/learn/courses/30/lessons/68647
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int even_row_checker(vector<vector<int>> b){
int sum;
for(int i=0; i<b.size(); ++i){
sum=0;
for(int j=0; j<b[0].size(); ++j){
if(b[i][j]) sum++;
}
if(sum%2) return 0;
}
return 1;
}
void r_combination(vector<vector<int>>& ret, int n, int r){
vector<int> index(n, 1);
for(int i=0; i<n-r; ++i) index[i]=0;
do{
ret.push_back(index);
}while(next_permutation(index.begin(), index.end()));
}
void cases(const vector<int>& allsize, vector<vector<int>>& ret, int r, vector<int> cur){
if(r==allsize.size()){
ret.push_back(cur);
return;
}
for(int i=0; i<allsize[r]; ++i){
cur.push_back(i);
cases(allsize, ret, r+1, cur);
cur.pop_back();
}
}
int solution(vector<vector<int>> a){
int answer=0, sum;
const int crt=10'000'000+19;
vector<int> col_count;
for(int i=0; i<a[0].size(); ++i){
sum=0;
for(int j=0; j<a.size(); ++j){
if(a[j][i]) sum++;
}
col_count.push_back(sum);
}
vector<vector<vector<int>>> all;
for(int i=0; i<col_count.size(); ++i){
vector<vector<int>> ret;
r_combination(ret, a.size(), col_count[i]);
all.push_back(ret);
}
// count each col cases
vector<int> allsize;
for(int i=0; i<all.size(); ++i) allsize.push_back(all[i].size());
vector<vector<int>> ret;
vector<int> tmp;
cases(allsize, ret, 0, tmp);
// i for ret index
for(int i=0; i<ret.size(); ++i){
vector<vector<int>> b(a.size(), vector<int>(a[0].size()));
// j for ret[i] index and col
for(int j=0; j<ret[i].size(); ++j){
// k for row
for(int k=0; k<b.size(); ++k){
b[k][j]=all[j][ret[i][j]][k];
}
}
answer+=even_row_checker(b);
answer%=crt;
}
return answer;
}
int main(void){
typedef vector<vector<int>> vector2;
vector2 a1={
{0, 1, 0},
{1, 1, 1},
{1, 1, 0},
{0, 1, 1}
};
vector2 a2={
{1, 0, 0},
{1, 0, 0}
};
vector2 a3={
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 1, 0, 0, 0},
{0, 0, 0, 0, 1}
};
int result1, result2, result3;
result1=solution(a1);
result2=solution(a2);
result3=solution(a3);
cout<<"result1: "<<result1<<endl;
cout<<"result2: "<<result2<<endl;
cout<<"result3: "<<result3<<endl;
return 0;
}
Beautiful string (Lv. 5)
https://school.programmers.co.kr/learn/courses/30/lessons/68938
#include <iostream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;
int beauti(string ss){
int len=ss.length();
int sum=0;
for(int i=0; i<len; ++i){
for(int j=i+1; j<len; ++j){
if(ss[i]!=ss[j]) sum= sum<j-i? j-i: sum;
}
}
return sum;
}
ll solution(const string s){
ll answer=0;
int len=s.length();
for(int i=0; i<len; ++i){
for(int j=1; j<len-i+1; ++j){
string ss=s.substr(i, j);
answer+=beauti(ss);
}
}
return answer;
}
int main(void){
string s1="baby";
string s2="oo";
ll result1, result2;
result1=solution(s1);
result2=solution(s2);
cout<<"result1: "<<result1<<endl;
cout<<"result2: "<<result2<<endl;
return 0;
}
Fake Hamiltonian (Lv. 5)
https://school.programmers.co.kr/learn/courses/30/lessons/70132

Not solved yet
#include <iostream>
#include <vector>
int solution(vector<vector<int>> t){
int answer=0;
return answer;
}
int main(void){
vector<vector<int>> t1={
{5, 1},
{5, 2},
{3, 5},
{3, 6},
{2, 4},
{4, 0}
};
vector<vector<int>> t2={
{2, 5},
{2, 0},
{3, 2},
{4, 2},
{2, 1}
};
int result1, result2;
result1=solution(t1);
result2=solution(t2);
cout<<"result1: "<<result1<<endl;
cout<<"result2: "<<result2<<endl;
return 0;
}